using System;
using System.Collections.Generic;
using System.Linq;

namespace LeetCode {
    public class tree {
        public bool IsScramble (string s1, string s2) {
            if (s1.Length != s2.Length) {
                return false;
            }
            if (s1 == s2) {
                return true;
            }
            char[] l1 = s1.ToCharArray ();
            char[] l2 = s2.ToCharArray ();
            Array.Sort (l1);
            Array.Sort (l2);
            for (int i = 0; i < s1.Length; i++) {
                if (l1[i] != l2[i])
                    return false;
            }
            for (int i = 1; i < s1.Length; i++) {
                if (IsScramble (s1.Substring (0, i), s2.Substring (0, i)) &&
                    IsScramble (s1.Substring (i, s1.Length - i), s2.Substring (i, s2.Length - i)))
                    return true;
                if (IsScramble (s1.Substring (0, i), s2.Substring (s2.Length - i, i)) &&
                    (IsScramble (s1.Substring (i, s1.Length - i), s2.Substring (0, s2.Length - i))))
                    return true;
            }
            return false;
        }
        public bool IsScramble1 (string s1, string s2) {
            if (s1.Length != s2.Length) {
                return false;
            }
            if (s1 == s2) {
                return true;
            }
            int n = s1.Length;
            bool[, , ] dp = new bool[n, n, n + 1];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    dp[i, j, 1] = s1[i] == s2[j];
                }
            }
            for (int len = 2; len <= n; len++) {
                for (int i = 0; i <= n - len; i++) {
                    for (int j = 0; j <= n - len; j++) {
                        for (int k = 1; k < len; k++) {
                            if ((dp[i, j, k] && dp[i + k, j + k, len - k]) || (dp[i + k, j, len - k] && dp[i, j + len - k, k])) {
                                dp[i, j, len] = true;
                            }
                        }
                    }
                }
            }
            return dp[0, 0, n];
        }
        public bool isScramble (string s1, string s2) {
            int n = s1.Length;
            bool[, , ] dp = new bool[n, n, n + 1];

            for (int i = n - 1; i >= 0; i--)
                for (int j = n - 1; j >= 0; j--)
                    for (int k = 1; k <= n - Math.Max (i, j); k++) {
                        if (s1.Substring (i, k) == (s2.Substring (j, k))) {
                            dp[i, j, k] = true;
                        } else {
                            for (int l = 1; l < k; l++) {
                                if (dp[i, j, l] && dp[i + l, j + l, k - l] || dp[i, j + k - l, l] && dp[i + l, j, k - l]) {
                                    dp[i, j, k] = true;
                                    break;
                                }
                            }
                        }
                    }
            return dp[0, 0, n];
        }
    }
}